import numpy as np
import math
import cmath


def decimal_to_binary(dec_number, n):
	'''
	将十进制数转为指定长度的二进制数
	dec_number:十进制数
	n:转换二进制的指定位数
	return : binary (string type)
	'''
	num = dec_number
	bin_num = ""
	while num != 0:
		bin_num = str(num%2) + bin_num
		num = num // 2

	while len(bin_num) < n:
		bin_num = "0" + bin_num
	#print(bin_num)
	return bin_num


def binary_to_decimal(bin_number):
	'''
	将二进制数转为十进制
	'''
	num = 0
	for i in range(len(bin_number)):
		num = int(num + int(bin_number[-1-i])*math.pow(2, i))
	#print(num)
	return num


def reverse_binary(bin_number):
	'''
	翻转二进制
	'''
	reverse_bin_num = ""
	for i in range(len(bin_number)):
		reverse_bin_num = reverse_bin_num + bin_number[-1-i]
	#print(reverse_bin_num)
	return reverse_bin_num


def binary_displacement(bin_number, n, d):
	'''
	二进制向左移d位
	bin_number : 二进制数
	n : 二进制位数
	d : 移位数
	'''
	pass


def reverse_order(Xn, N):
	#print(Xn_copy)
	Xn_copy = Xn.copy()
	L = math.log2(N)
	for i in range(N):
		s = decimal_to_binary(i, L)
		s_r = reverse_binary(s)
		i_r = binary_to_decimal(s_r)
		if s == s_r:
			pass
		elif i < i_r:
			#print(Xn_copy[i])
			t = Xn_copy[i]
			Xn_copy[i] = Xn_copy[i_r]
			Xn_copy[i_r] = t
		else:
			pass
	#print(Xn_copy)
	return Xn_copy

def get_rotation_factor(N):
	'''
	得到旋转因子
	'''
	rotation_factor = []
	for i in range(N//2):
		rotation_factor.append(cmath.exp(complex(0,-1)*(2*cmath.pi/N)*i))
	return rotation_factor


def get_r_value(k, L):
	k_b = decimal_to_binary(k, L)
	return 
